// 题目描述：
// 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。



// 示例 1：

// 输入：nums = [3,2,3]
// 输出：3
// 示例 2：

// 输入：nums = [2,2,1,1,1,2,2]
// 输出：2

// 自己的答案：
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let i = nums.length;
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            map.set(nums[i], map.get(nums[i]) + 1)
        } else {
            map.set(nums[i], 1)
        }
        if (map.get(nums[i]) >= nums.length / 2) {
            return nums[i]
        }
    }
    // while (i--) {
    //     if (map.get(nums[i])) {
    //         map.set(nums[i], ++map.get(nums[i]))
    //     } else {
    //         map.set(nums[i], 0)
    //     }
    //     if(map.get(nums[i]) > nums.length /2) {
    //         return nums[i]
    //     }
    // }
};

// Gpt精简：
/**  
 * @param {number[]} nums  
 * @return {number}  
 */
var majorityElement = function (nums) {
    const map = new Map();
    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
        if (map.get(num) > nums.length / 2) {
            return num;
        }
    }
};

// 官方答案：
// 排序数组，如果有一个数字出现的频率大于n/2，则在数组nums. length/2的位置就是这个数;
var majorityElement = function (nums) {
    nums.sort((a, b) => a - b)
    return nums[Number(nums.length / 2)]
};

// 摩尔股票法：
var majorityElement = function (nums) {
    let count = 1;
    //将第一个数献于majority
    let majority = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            majority = nums[i];
        }
        if (nums[i] === majority) {
            count++;
        } else {
            count--;
        }
        return majority;
    }
}